package com.datastructure.linkedlist;

/**
 * @author: 临晖
 * @date: 2023/10/11
 * @description:
 */
public class Solution06 {

    public ListNode detectCycle(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;
        boolean flag = false;
        while (fast != null && slow != null) {
            if (fast.next == null) { 
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                flag = true;
                break;
            }
        }

        //如果flag 为 false 则没有环
        if (!flag) {
            return null;
        }

        //slow = x + y
        //fast = x + y + n(y + z)
        //2 * (x + y) = x + y + n(y + z)
        //x + y = n(y + z)
        //x = (n - 1)(y + z) + z
        //当n = 1时，x = z
        //这里是x = z的关系
        //慢指针肯定走的没超过一圈
        //快指针大于等于一圈
        ListNode curr = head;
        while (true) {
            if (curr == fast) {
                return curr;
            }
            //x = z
            curr = curr.next;
            fast = fast.next;
        }


    }
}
